◀ Prev · Parts · Full · Next ▶

In the problem of unrelated-machines scheduling, there are some m different machines that should process some n different jobs. When machine i processes job j, it takes time pi,j. The goal is to partition the jobs among the machines such that maximum completion time of a machine is as small as possible. The decision version of this problem is: given time T, is there a partition in which the completion time of all machines is at most T?

For each machine i, there are finitely many subsets of jobs that can be processed by machine i in time at most T. Each such subset is called a configuration for machine i. Denote by Ci(T) the set of all configurations for machine i, given time T. For each machine i and configuration c in Ci(T), define a variable x i , c {\displaystyle x_{i,c}} which equals 1 iff the actual configuration used in machine i is c, and 0 otherwise. Then, the LP constraints are:

• ∑ ∑ c ∈ ∈ C i ( T ) x i , c = 1 {\displaystyle \sum _{c\in C_{i}(T)}x_{i,c}=1} for every machine i in 1,...,m;

• ∑ ∑ i = 1 m ∑ ∑ c ∋ ∋ j , c ∈ ∈ C i ( T ) x i , c = 1 {\displaystyle \sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1} for every job j in 1,...,n;

• x i , j ∈ ∈ { 0 , 1 } {\displaystyle x_{i,j}\in \{0,1\}} for every i, j.

The integrality gap of the configuration-LP for unrelated-machines scheduling is 2.cite-ref-0-5-1[5]

◀ Prev · Parts · Full · Next ▶